Searching through collections (referred to herein by the generic term "files") of data records for those records that have a particular characteristic, is an important and often-performed activity in a wide variety of computer applications. In telephony, for example, routing tables must be searched for each attempted call in order to find a route that corresponds to the dialed number. One of two techniques is conventionally employed for searching: a binary search or a hashing search. This application relates to the binary search.
If all possible sequential data records within a range of record values are included in a file, it is desirable to enter in the table, list, database, or other representation of the file, merely an indication that the whole range is included, as opposed to individually entering therein each record that is within the range. This serves to markedly reduce the size of the representation of the file. In telephony, for example, it is common that all telephone numbers within a range are valid numbers and all have the same route associated therewith. The size of the routing table is significantly reduced if the table contains as an entry the range limits in association with the route, as opposed to containing a separate entry for each telephone number within the range.
In conventional implementations of searchable files, indications of included ranges are made as double-width entries. That is, fields within a single data record are used to store both the upper and the lower limit of the range. In telephony routing tables, where each entry typically occupies a single word of memory, it means that the memory words have to be wide enough to store side-by-side the two telephone numbers that represent the range limits, along with the route number.
This way of representing ranges produces problems. Firstly, this approach requires the use of wider-than-normal, e.g., double-width, memories in order to accommodate words of the requisite width. Use of such memories entails additional cost, especially in conjunction with hardware implementations of search mechanisms. Secondly, during a binary search, this approach requires an additional compare operation per examined entry: the searched-for data record has to be compared against both range limits that are included in the entry. Doubling of the required number of sequential software operations markedly increases the search time. Consequently, inclusion of range entries within binary-searchable files of data entries has typically produced a mixed blessing of advantages and disadvantages.